import java.util.ArrayList;
import java.util.List;

public class Leetcode {
}

//leetcode:494:目标和
class Solution1 {
    int sum = 0;
    int ret = 0;
    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums,0,target);
        return ret;
    }
    public void dfs(int[] nums,int pos,int target){
        if (pos == nums.length) {
            if (sum == target) {
                ret++;
            }
            return;
        }
        sum += nums[pos];
        dfs(nums,pos+1,target);
        sum -= nums[pos];//回溯

        sum -= nums[pos];
        dfs(nums,pos+1,target);
        sum += nums[pos];//回溯

    }
}


//leetcode:77:组合
class Solution2 {
    List<List<Integer>> ret;
    List<Integer> path;
    public List<List<Integer>> combine(int n, int k) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(n,1,k);
        return ret;
    }
    public void dfs(int n,int pos,int k){
        if(path.size() == k){
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i = pos;i <= n;i++){
            path.add(i);
            dfs(n,i+1,k);
            path.remove(path.size()-1);
        }
    }
}

//leetcode:39:组合总和
class Solution3 {
    List<List<Integer>> ret;
    List<Integer> path;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(candidates,target,0);
        return ret;
    }
    public void dfs(int[] candidates,int target,int pos){
        if(pos == candidates.length){
            return;
        }
        //如果target等于0，就代表找到了这一组数据
        if(target == 0) {
            ret.add(new ArrayList<>(path));
            return;
        }
        //如果target大于0，就继续往下找
        if(target > 0){
            //遍历数组，从前一个元素位置开始去找下一个数，让target去减，直到target等于0
            for(int i = pos ;i < candidates.length ;i++){
                path.add(candidates[i]);
                dfs(candidates,target-candidates[i],i);
                //回溯
                path.remove(path.size()-1);
            }
        }
    }
}

//leetcode:784:字母大小写的全排列
class Solution4 {
    List<String> ret;
    StringBuilder path;
    public List<String> letterCasePermutation(String s) {
        ret = new ArrayList<>();
        path = new StringBuilder();
        dfs(s,0);
        return ret;
    }

    public void dfs(String s,int pos){
        if(path.length() == s.length()){
            ret.add(path.toString());
            return;
        }
        //不进行转换的存入
        char ch = s.charAt(pos);
        path.append(ch);
        dfs(s,pos+1);
        path.deleteCharAt(path.length()-1);

        //将字母进行转换的存入
        if(ch < '0' || ch > '9'){
            char tmp = change(ch);//转换字母大小写
            path.append(tmp );
            dfs(s,pos+1);
            path.deleteCharAt(path.length()-1);
        }
    }

    public char change(char ch){
        if(ch >= 'a' && ch <= 'z'){
            return ch -= 32;//转换成大写
        }else{
            return ch += 32;//转换成小写
        }
    }
}